package 二叉树;


/**
 * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 *
 * 题解：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solutions/240096/236-er-cha-shu-de-zui-jin-gong-gong-zu-xian-hou-xu/
 */
public class _236_二叉树的最近公共祖先 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 终止条件
        // 当越过叶节点，直接返回null；或者当root等于p和q的时候，直接返回root
        if(root == null || root == p || root == q) return root;

        //递归左子节点
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        //递归右子节点
        TreeNode right = lowestCommonAncestor(root.right,p,q);

        // left为null，则p、q都在root的right
        if(left == null) return right;
        // right为null，则p、q都在root的left
        if(right == null) return left;

        // left和right不等于null，则返回root
        return root;
    }
}
